/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/power-of-four
   @Language: C++
   @Datetime: 19-05-23 13:37
   */

// Method 1, log and power, 50ms
class Solution {
public:
	/**
	 * @param num: an integer
	 * @return: whether the integer is a power of 4
	 */
	bool isPowerOfFour(int num) {
		// Write your code here
		if(num==0) return false;
		return num==(int)pow(4,(int)(log(num)/log(4)+0.5));
	}
};

// Method 2, search table, Time 50ms
class Solution {
public:
	/**
	 * @param num: an integer
	 * @return: whether the integer is a power of 4
	 */
	bool isPowerOfFour(int num) {
		// Write your code here
		unordered_set<int> powfours={1,1<<2,1<<4,1<<6,1<<8,1<<10,1<<12,1<<14,
			1<<16,1<<18,1<<20,1<<22,1<<24,1<<26,1<<28,1<<30};
		return powfours.count(num);
	}
};
